package com.daji.search_and_sort;

import java.util.Arrays;

//参考文章：https://zhuanlan.zhihu.com/p/124356219
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {7, 6, 12, 11, 5, -12, 0, 3, 7, 20};
        merge_sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void merge_sort(int[] arr) {
        int len = arr.length;
        //事先申请一个【原数组len】大小的数组，作为一个辅助空间。所以该算法空间复杂度是 O(n)
        int[] result = new int[len];
        merge_sort_recursive(arr, result, 0, len - 1);
    }

    // 归并排序（Java-递归版）
    static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
        //整个待归并的序列必须大于1（也就是2及2以上），因为后面还会根据mid分成两个待排序序列，如果是1及1以下的话，就无法再分了.
        if (start >= end)
            return;
        int mid = (start+end)/2;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        merge_sort_recursive(arr, result, start1, end1);
        merge_sort_recursive(arr, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2) {  //只要arr[start1]或arr[start2]有东西，就一直比较.

            //比较归并的两个头指针，谁更小谁就排在辅助空间的头部位置。
            //下面的if和else可以被这一行代码简化：result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            if (arr[start1] < arr[start2]) {
                result[k] = arr[start1];
                k++;
                start1++;
            }else {
                result[k] = arr[start2];
                k++;
                start2++;
            }
        }
        //如果待排序序列2已经排完了，待排序序列1还有元素，那么就将待排序序列1剩下元素无条件追加到辅助空间中
        while (start1 <= end1)
            result[k++] = arr[start1++];
        //如果待排序序列1已经排完了，待排序序列2还有元素，那么就将待排序序列2剩下元素无条件追加到辅助空间中
        while (start2 <= end2)
            result[k++] = arr[start2++];
        //将排好序的结果数组的值赋值给原数组
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }


}
